/*
 * Copyright (C), 2015-2018
 * FileName: Solution041
 * Author:   zhao
 * Date:     2018/12/3 17:40
 * Description: 41. 缺失的第一个正数
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

/**
 * 〈一句话功能简述〉<br>
 * 〈41. 缺失的第一个正数〉
 *
 * @author zhao
 * @date 2018/12/3 17:40
 * @since 1.0.1
 */
public class Solution041 {
    /**************************************
     * 题目
     给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

     说明:
     你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

     示例 1:

     输入: [1,2,0]
     输出: 3
     示例 2:

     输入: [3,4,-1,1]
     输出: 2
     示例 3:

     输入: [7,8,9,11,12]
     输出: 1
     **************************************/

    /**************************************

     想法：
     1. 错了！使用二进制来存储，将第N位的数据改成1，原来想的有二十亿数据，后面发现int只有32位，只能保证32个，错了

     2. 交换法

     将1放到数组 索引0位置，将2放到数组 索引1的位置，将3放到数组索引1的位置
     //假设交换的数据还是大于0且<i+1，则放在合适的位置,且数据不相等，避免死循环
     用的是 if判断  加上  i--,别的方法使用while循环

     然后去循环数组，数据不对就返回

     我的做法

     超过97%的测试案例

     时间复杂度/空间复杂度：O(n)/1

     代码执行过程：

     总结：

     * ***********************************/
    public int firstMissingPositive(int[] nums) {

        if (nums.length == 0) {
            return 1;
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                // 假设交换的数据还是大于0且<i+1，则放在合适的位置,且数据不相等，避免死循环
                if (nums[i] < nums.length + 1 && nums[i] != nums[nums[i] - 1]) {
                    int tmp = nums[nums[i] - 1];
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = tmp;
                    i--;
                }
            }
        }

        // 然后去循环数组，数据不对就返回
        for (int i = 0; i < nums.length; i++) {
            if (i + 1 != nums[i]) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

    /**
     * 位运算，错误答案
     * @param nums
     * @return
     */
    public int bit(int[] nums) {
        long bitNum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                // 将bitNum的第nums[i]变为1
                // 第 i 位与0 或，值不变。第 i 位与1 或，变成1。因此，我们的目标是 num 与 一个第 i 位值为1，其它位的值都为0的数相 或
                bitNum = bitNum | (1 << nums[i]);
            }
        }

        for (int i = 1; i < nums.length + 1; i++) {
            boolean zeroBit = (bitNum & (1 << i)) == 0;
            if (zeroBit) {
                return i;
            }
        }

        return nums.length + 1;
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public int better(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}
